package day0;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class code1 {

    public void moveZeroes(int[] nums) {
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]!=0){
                nums[index]=nums[i];
                index += 1;
            }
        }
        for(int i=index; i<nums.length; i++){
            nums[index] = 0;
        }
    }

    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length-1;
        int max = 0;

        while (left<right){
            int h = Math.min(height[left],height[right]);
            max = Math.max(max,(right-left)*h);
            if(height[left]<height[right]){
                left += 1;
            }else {
                right -=1;
            }
        }
        return max;
    }

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();

        Arrays.sort(nums);
        for (int i=0;i<nums.length-2;i++){
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }
            int sum = -nums[i];
            int left = i+1;
            int right = nums.length-1;

            ArrayList<Integer> l = new ArrayList<>();
            l.add(nums[i]);
            l.add(Integer.MIN_VALUE);
            l.add(Integer.MAX_VALUE);

            while (left<right){
                if(nums[left]+nums[right]==sum){
                   if(l.get(1)!=nums[left] && l.get(2)!=nums[right]){
                       l.remove(1);
                       l.remove(2);
                       l.add(nums[left]);
                       l.add(nums[right]);
                       list.add(new ArrayList<>(l));
                   }
                   left += 1;
                   right -= 1;
                }else if(nums[left]+nums[right]<sum){
                    left += 1;
                }else {
                    right -= 1;
                }
            }
        }
        return list;
    }

    public int trap(int[] height) {
        int[] left = new int[height.length];
        int[] right = new int[height.length];

        left[0] = 0;
        for(int i =1;i<height.length;i++){
            left[i] = Math.max(left[i-1],height[i-1]);
        }

        right[height.length-1] = 0;
        for(int j=height.length-2;j>=0;j--){
            right[j] = Math.max(right[j+1],height[j+1]);
        }

        int sum = 0;
        for (int i = 0; i < height.length; i++) {
            int min = Math.min(left[i],right[i]);
            if(min>height[i]){
                sum += min-height[i];
            }
        }

        return sum;
    }

}
